package study.算法Algorithm.查找算法.二分查找;

import java.util.ArrayList;
import java.util.List;

//当数组中有重复的时，将重复的值都查到
public class BinarySearch2 {
    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 89, 89, 1000, 1234};
        List resIndex = m01(arr, 0, arr.length - 1, 89);
        System.out.println("resIndex = " + resIndex);
    }

    /*
        思路：
            1、在经过递归后，找到的mid值不要立马返回
            2、向mid索引值的左边扫描，将所有满足查找值的下标加入到集合中
            3、向mid索引值的右边扫描，将所有满足查找值的下标加入到集合中
     */
    private static List m01(int[] arr, int left, int right, int findVal) {
        //当left>right时，说明递归整个数组后，没有找到
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {  //向右递归查找
            return m01(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {  //向左边递归
            return m01(arr, left, mid - 1, findVal);
        } else {
            List<Integer> list = new ArrayList<>();
            //向mid索引值的左边扫描，将所有满足查找值的下标加入到集合中
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                } else {
                    list.add(temp);
                    temp--;
                }
            }

            list.add(mid);

            //向mid索引值的右边扫描，将所有满足查找值的下标加入到集合中
            temp = mid + 1;
            while (true) {
                if (temp > right || arr[temp] != findVal) {
                    break;
                } else {
                    list.add(temp);
                    temp++;
                }
            }
            return list;
        }
    }
}
